package tree.leetcode_110_easy;

/**
 * 自底向上递归
 */
public class IsBalancedBest {
    public boolean isBalanced(TreeNode root) {
        return getDepth(root) != -1;
    }
    public int getDepth(TreeNode root) {
        // 空树深度为 0
        if (root == null) {
            return 0;
        }
        // 计算左子树的高度
        int left = getDepth(root.left);
        // 如果递归过程发现左子树已经不是平衡二叉树了，提前返回，后面不用再判断了
        if (left == -1) {
            return -1;
        }
        // 计算右子树的高度
        int right = getDepth(root.right);
        // 右子树同理
        if (right == -1) {
            return -1;
        }
        // 如果当前子树不是平衡二叉树，返回 -1
        if (Math.abs(left - right) > 1) {
            return -1;
        }
        return Math.max(left, right) + 1;
    }
}
